package algorithm.middle;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: CheckValidString678
 * @description:
 * 给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
 *
 *     任何左括号 ( 必须有相应的右括号 )。
 *     任何右括号 ) 必须有相应的左括号 ( 。
 *     左括号 ( 必须在对应的右括号之前 )。
 *     * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
 *     一个空字符串也被视为有效字符串。
 *
 * @date 2020/9/220:14
 * @since V1.0
 */
public class CheckValidString678 {

    public static void main(String[] args) {

    }
    //贪心算法
    public boolean checkValidString(String s) {
        byte[] bytes = s.getBytes();
        int min = 0;
        int max = 0;
        for (int i=0;i<bytes.length;i++){
            if (bytes[i]=='('){
                //匹配左括号
                min++;
                max++;
            }else if (bytes[i]==')'){
                //匹配右括号
               if (min>0)min--;
               if (max--==0) return false;
            }else {
                //匹配星号
               if (min>0) min--;
               max++;
            }

        }
        return min==0;
    }
}
